#include <stdio.h>
#include <stdlib.h>

typedef struct _node {
	int value;
	int index;
	struct _node *next;
} Node;

typedef struct _list{
	Node *head;
	Node *tail;
	int len;
} List;

void initList(List *pList)
{
	pList->head = NULL;
	pList->tail = NULL;
	pList->len = 0;
}

void addNode(List *pList, int value)
{
	Node *pNode = (Node *)malloc(sizeof(Node));
	pNode->value = value;
	pNode->next = NULL;
	
	if(pList->head == NULL){
		pList->head = pNode;
		pList->tail = pNode;
		pList->head->index = 0;
		pList->tail->index = 0;
	}else{
		pNode->index = pList->tail->index + 1;
		pList->tail->next = pNode;
		pList->tail = pNode;		
	}
	pList->len++;	
}

int findNodeByIndex(List *pList, int index)
{
	Node *pNode;
	int res = 0;
	
	if(index < pList->len){
		for(pNode = pList->head; pNode; pNode = pNode->next){
			if(index == pNode->index){
				res = pNode->value;	
			}
		}
	}	
	
	return res;	
}

int findNodeByValue(List *pList, int value)
{
	Node *pNode;
	int index = 0;
	
	for(pNode = pList->head; pNode; pNode = pNode->next){
		if(value == pNode->value){
			index = pNode->index;	
		}
	}
		
	return index;	
}

void deleteNodeByIndex(List *pList, int index)
{
	Node *pNode, *pLastNode;
	int i;
	if(index < pList->len){
		if(index == 0){
			free(pList->head);
			pList->head = pList->head->next;			
			pList->len--;
		}else{
			for(pNode = pList->head; pNode; pLastNode = pNode, pNode = pNode->next){
				if(pNode->index == index){
					pLastNode->next = pNode->next;
					free(pNode);
					pList->len--;
				}
			}
		}
			
		for(pNode = pList->head, i = 0; pNode; pNode = pNode->next, i++){
			pNode->index = i;
		}	
	}
}

void insertNodeBeforeIndex(List *pList, int index, int value)
{
	Node *pNewNode = (Node *)malloc(sizeof(Node));
	pNewNode->value = value;
	
	Node *pNode;
	int i;
	if(index < pList->len){
		if(index == 0){
			pNewNode->next = pList->head;
			pList->head = pNewNode;
			pList->len++;
		}else{
			for(pNode = pList->head; pNode; pNode = pNode->next){
				if(pNode->index == (index - 1)){
					pNewNode->next = pNode->next;	
					pNode->next = pNewNode;					
					pList->len++;
				}
			}
		}
			
		for(pNode = pList->head, i = 0; pNode; pNode = pNode->next, i++){
			pNode->index = i;
		}	
	}	
}

void deleteList(List *pList)
{
	Node *pNode, *pNextNode;
	for(pNode = pList->head; pNode; pNode = pNextNode){
		pNextNode = pNode->next;
		free(pNode);
	}
	pList->head = NULL;
	pList->tail = NULL;
	pList->len = 0;
}

void printList(List *pList)
{
	Node *pNode;
	printf("List length = %d\n", pList->len);
	printf("List element: \n");
	for(pNode = pList->head; pNode; pNode = pNode->next)
	{
		printf("index[%d]: %d\t", pNode->index, pNode->value);
	}
	printf("\n");
}

#define TEST_INDEX 3
#define TEST_VAL 12

int main()
{
	List list;	
	initList(&list);
	
	int number;
	do {
		scanf("%d", &number);
		if(number != -1) {
			addNode(&list, number);			
		}
	} while(number != -1);
	
	printList(&list);	
	
	//printf("index[%d]:%d\n", TEST_INDEX, findNodeByIndex(&list, TEST_INDEX));
	
	//printf("index of value %d is: [%d]", TEST_VAL, findNodeByValue(&list, TEST_VAL));
	
	deleteNodeByIndex(&list, 0);
	printList(&list);
	
	insertNodeBeforeIndex(&list, 0, 111);
	printList(&list);
	
	insertNodeBeforeIndex(&list, 3, 222);
	printList(&list);
	
	deleteList(&list);
	printList(&list);

	return 0;
}
